package com.shuyun.xxx.guava.algorithm;

import java.util.Scanner;
import java.util.jar.Pack200;

/**
 * Created by goodb on 2017/5/9.
 */
public class Tree {
    private String data;
    private Tree left;
    private Tree right;
    Scanner sc = new Scanner(System.in);

    public Tree init(){
        Tree tree = new Tree();
        if(tree != null){
            tree.data = sc.next();
            tree.left = null;
            tree.right = null;
            return tree;
        }
        return null;
    }

    public void addTreeNode(Tree node){
        Tree pNode, parent;
        String pData;
        int whichNode;
        if((pNode = new Tree()) != null){
            pNode.data = sc.next();
            pNode.left = null;
            pNode.right = null;
            pData = sc.next(); //父节点数据
            parent =findTreeNode(node, pData);
            if(parent == null){
                pNode = null; //没有找到父节点
                return;
            }
            whichNode = sc.nextInt();
            do{
                if(whichNode == 1 || whichNode == 2){
                    switch (whichNode){
                        case 1:
                            if(parent.left != null){
                                //左边已经有了
                            }else{
                                parent.left = pNode;
                            }
                            break;
                        case 2:
                            if(parent.right != null){
                                //右边已经有了
                            }else{
                                parent.right = pNode;
                            }
                            break;
                        default:
                            //参数无效
                    }
                }
            }while(whichNode != 1 || whichNode != 2);
        }
    }

    public Tree findTreeNode(Tree node, String data){
        Tree result;
        if(node == null){
            return null;
        }else{
            if(node.data.equals(data)){
                return node;
            }else{
                if((result = findTreeNode(node.left, data)) != null){
                    return result;
                }else if((result = findTreeNode(node.right, data)) != null){
                    return result;
                }else{
                    return null;
                }
            }
        }
    }

    public Tree treeLeftNode(Tree node){
        if(node != null){
            return node.left;
        }else{
            return null;
        }
    }

    public Tree treeRightNode(Tree node){
        if(node != null){
            return node.right;
        }else{
            return null;
        }
    }

    public int treeDepth(Tree node){
        int leftDepth, rightDepth;
        if(node == null){
            return 0;
        }else{
            leftDepth = treeDepth(node.left);
            rightDepth = treeDepth(node.right);
            if(leftDepth > rightDepth){
                return leftDepth + 1;
            }else{
                return rightDepth + 1;
            }
        }
    }

    public void DLR(Tree node){
        if(node != null){
            System.out.println(node.data);
            DLR(node.left);
            DLR(node.right);
        }
    }

}
